Inteligencia Artificial

1 Contenido de la clase

Repaso de A* y su optimalidad [03:54-28:44]

A* combina las dos búsquedas previas: f(n) = g(n) + h(n), donde g(n) es el costo acumulado del camino (búsqueda de costo uniforme/Dijkstra) y h(n) la heurística (búsqueda avara). Se expande siempre el nodo con f más pequeña. En el ejemplo desde F hacia B, E y G se tienen f = 2+6=8, 4+2=6 y 9+1=10 [03:54-08:30].

Si la heurística engaña, A* puede tomar el camino equivocado: ir de F a C cuesta 5 con h=0 (f=5) y de F a A cuesta 1 con h=5 (f=6), así que se va "por abajo", pero el camino corto real es F→A (1) + A→C (3) = 4: "la heurística no nos está ayudando mucho" [08:30-09:10].

Una heurística admisible nunca sobrestima el costo real óptimo restante: h(n) ≤ h*(n); es una heurística optimista. En la meta h(n) = 0 y, si h = 0 en todos los nodos, A* se vuelve búsqueda de costo uniforme. La distancia en línea recta (euclidiana) es admisible en mapas porque es el camino más corto posible entre dos puntos [07:04-08:29 · 29:36-41:20].

Los problemas relajados son fuente de heurísticas: viajar de ciudad a ciudad se relaja permitiendo "volar en línea recta"; en problemas con enteros se permite usar fracciones. Heurísticas inadmisibles a veces son útiles en problemas muy complejos donde basta encontrar alguna solución. [41:20-41:40]

f(n) = g(n) + h(n) · h(n) ≤ h*(n) [03:54-08:29]

Demostración de optimalidad (argumento de la frontera): si la meta A está en la frontera y g(A) < g(B) para cualquier nodo subóptimo B, con h(A) = 0 y h admisible se cumple f(A) ≤ f(B); por lo tanto la meta óptima se extrae (expande) antes que cualquier nodo subóptimo. Conclusión: hay que detenerse al extraer la meta, no basta con generarla en la frontera. Todos los ancestros de la meta óptima salen antes que cualquier nodo subóptimo [21:00-28:44].

Búsqueda en árbol vs. en grafo y consistencia [41:20-49:33]

Nunca, nunca expandir un estado dos veces (evita ciclos). Se mantiene un conjunto cerrado de estados ya expandidos: "búsqueda de árbol más un conjunto de estados ya expandidos". Ejemplo: desde F se va a B (f=2) en vez de A (f=5); el camino óptimo F-B-G cuesta 5 y F-A-C cuesta 6 [41:20-45:57].

Consistencia (monotonicidad): para cada arco, h(n) ≤ c(n, n') + h(n'). En la práctica la heurística no debe bajar más de lo que cuesta la arista (desigualdad del triángulo, como la distancia en línea recta). La consistencia implica admisibilidad (se demuestra por inducción). [46:18-49:33]

h(n) ≤ c(n, n') + h(n') [46:18-49:33]

Algoritmo de búsqueda en grafo: se inserta el nodo inicial en la frontera; en cada ciclo, si la frontera está vacía → fallo; se extrae el nodo con menor f; si es meta → solución; se agrega a los visitados y se expande insertando los sucesores no visitados. El detalle está en "Inteligencia Artificial: un enfoque moderno" (Russell y Norvig) [61:40-64:45].

Problemas de satisfacción de restricciones (CSP) [65:15-68:43]

El profesor propone resolver un sudoku y pregunta qué tan bien funcionarían ahí la búsqueda en profundidad, la búsqueda en anchura o A*. Esta parte del curso trata los problemas de satisfacción de restricciones: estados definidos por variables Xi con valores de un dominio D, y la meta es un conjunto de restricciones sobre combinaciones de valores de subconjuntos de variables. [65:15-68:43]

En el sudoku las variables son las celdas vacías, el dominio es {1,...,9} y las restricciones exigen que cada fila, columna y región de 3×3 tenga valores distintos. Otros ejemplos de la conferencia: coloreado de mapas (estados adyacentes con colores distintos), criptoaritmética y el problema de las N-reinas. Aquí importa la asignación completa, no el camino; todos los caminos tienen la misma profundidad (conferencia).

Tipos de CSP: variables discretas (dominios finitos, tamaño O(d^n) → satisfactibilidad booleana; dominios infinitos → calendarización de trabajos) y continuas (lineales → programación lineal; no lineales → programación no lineal). Restricciones fuertes (unarias, binarias, de orden superior) y suaves (preferencias que agregan costo, p. ej. "rojo es mejor que verde") (conferencia).

Backtracking: se fija una variable a la vez (las variables son conmutativas), se revisan las restricciones en cada paso y solo se prueban valores sin conflicto con las asignaciones previas; resuelve N-reinas para N ≈ 25. Mejoras: filtrado (forward checking, consistencia de arcos AC-3) y ordenamiento (MRV: la variable con menos valores disponibles; LCV: el valor que menos restringe a las demás) (conferencia).

[parte no entendida] en varios pasajes de la grabación (bloques [09:10-20:00], [29:52-40:00] y [47:35-60:00] muy ruidosos).

Complementos y precisiones (para completar el tema)

• A* en grafo y heurísticas inconsistentes. Con heurística consistente, A* en grafo nunca necesita reabrir un nodo ya cerrado. Con heurística solo admisible pero inconsistente, hay que reabrir nodos al encontrar un camino más barato (o guardar el mejor g visto): el primer camino hallado a un estado puede no ser el óptimo.
• "No expandir dos veces" ≠ solo evitar ciclos: sin el conjunto cerrado, la búsqueda en grafo se vuelve un árbol exponencial con estados repetidos.
• Tipos de consistencia (más allá de AC-3): de nodo (restricciones unarias), de arco (binarias, AC-3), de camino (triples de variables) y k-consistencia. Complejidad de AC-3: O(c·d³).
• Límite de AC-3: tras propagar puede quedar una solución, varias, o ninguna sin saberlo. Ejemplo: colorear Australia con 2 colores; AC-3 no lo detecta, la consistencia de camino sí.
• Restricciones globales: Alldiff (todos distintos, como en sudoku/criptoaritmética) y Atmost (p. ej. Atmost(10, P1..P4)).
• Mejoras de backtracking (el libro): backjumping dirigido por conflictos, aprendizaje de restricciones y descomposición en árbol / conjuntos de corte.

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

Tarea 1 (en revisión): cada alumno eligió su tema/dominio según su área de origen (lenguaje natural, informática/robótica, etc.). Tras entregarla hay ~10 días de revisión y luego se convoca por correo a una reunión para validarla [00:00-03:00].

Asesorías con estudiantes ayudantes (reparto alfabético, al menos 1 hora/semana): el listado con correos se publicará en Classroom [00:00-03:00].

Examen 1: 1 de octubre — repasar A*, admisibilidad, consistencia y empezar CSP.

Checklist sugerido para estudiar:

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

El profesor mencionó el libro de referencia y, en la conferencia, varias bibliotecas de CSP. No dio URLs propias.

6 Glosario de términos

• Heurística admisible: h(n) ≤ h*(n); nunca sobrestima el costo óptimo restante a la meta [07:04-08:29].
• Consistencia (monotonicidad): h(n) ≤ c(n, n') + h(n'); implica admisibilidad [46:18-49:33].
• Conjunto cerrado: estados ya expandidos que no se vuelven a visitar en la búsqueda en grafo [41:20-45:57].
• CSP (Problema de satisfacción de restricciones): variables con dominios y restricciones; la solución es una asignación completa [65:15-68:43].
• Backtracking: fija una variable a la vez probando solo valores sin conflicto con asignaciones previas (conferencia).
• Forward checking (revisión hacia adelante): elimina del dominio de variables futuras los valores que violan restricciones al hacer una asignación (conferencia).
• AC-3: algoritmo de consistencia de arcos para propagar restricciones (conferencia).
• MRV: elegir la variable con menos valores disponibles; LCV: elegir el valor que menos restringe a las demás variables (conferencia).
• Restricciones suaves: preferencias que agregan costo a la asignación en vez de prohibirla (conferencia).
• Consistencia de nodo / arco / camino / k-consistencia: grados de propagación; de nodo (unarias), de arco (binarias), de camino (triples de variables).
• Alldiff / Atmost: restricciones globales (todos distintos / a lo más N en total) con propagación propia.
• Backjumping: backtracking que salta a la variable culpable del conflicto en vez de retroceder paso a paso.
• MAC: mantener la consistencia de arcos durante la búsqueda en profundidad.

7 Mapa mental textual

• Inteligencia Artificial · Clase 5
  • Repaso de A*
    • f(n) = g(n) + h(n); expandir el menor f
    • Heurística admisible: h(n) ≤ h*(n)
    • Optimalidad: detenerse al extraer la meta
    • Problemas relajados como fuente de heurísticas
  • Búsqueda en árbol vs. en grafo
    • Conjunto cerrado: no expandir un estado dos veces
    • Consistencia: h(n) ≤ c(n, n') + h(n')
    • Consistencia ⇒ admisibilidad
  • CSP
    • Variables, dominios y restricciones
    • Ejemplos: sudoku, coloreado de mapas, N-reinas
    • Backtracking + filtrado (forward checking, AC-3)
    • Ordenamiento MRV / LCV
  • Administrativo
    • Tarea 1 en revisión; asesorías por ayudantes
    • Examen 1: 1 de octubre